/*
题目: 活字印刷
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

注意：本题中，每个活字字模只能使用一次。

https://leetcode.cn/problems/letter-tile-possibilities
 */
public class NumTilePossibilities {
    int src = 0;
    int n ;
    boolean[] visited = new boolean[26];

    public int numTilePossibilities(String tiles) {
        n = tiles.length();
        char[] title = tiles.toCharArray();
        Arrays.sort(title);

        backTrack(title, 0);
        return src;
    }

    private void backTrack(char[] title, int offset) {
        if (offset >= n) {
            return ;
        }

        for (int i = 0; i < n; i++) {
            // 如果相等, 这个树枝 会被 上一条树枝所包含
            if (visited[i])
                continue ;
            if (i > 0 && title[i] == title[i - 1] && !visited[i - 1]) {
                continue ;
            }
            visited[i] = true;
            src ++;
            backTrack(title, offset + 1);

            visited[i] = false;
        }
    }
}
